Technical Field
This invention generally relates to an iterative refinement apparatus for solving linear systems of equations and, more particularly, provides an iterative refinement apparatus for generating data defining a solution vector for such a linear system.
Description of the Related Art
The solution of linear systems of equations is fundamental to numerous scientific and engineering applications. Efficient solutions of large scale linear systems is critical for achieving high energy efficiency and fast turn-around times, as well as permitting handling of increasingly-complex problems in the real-world application in question.
Linear systems can be generally represented by Ax=b, where A is a (typically symmetric, positive-definite) matrix of dimensions n×n (i.e., n rows and n columns), and b is a vector of dimensions n×1 (n rows and 1 column). Linear system solvers provide a processing apparatus for processing input data, defining the elements of matrix A and vector b to generate data defining the solution vector x for the system. The processing operation can be performed in accordance with various known techniques for solving linear systems. These techniques can generally be divided into direct methods, which aim to provide a solution in a fixed number of steps, and iterative methods. Iterative methods aim to improve on a current solution in each successive iteration until a desired precision is achieved.
The acceleration of linear system solvers is of high interest for many applications, particularly those involving large-scale linear systems. A standard way to accelerate the solving process is through use of a mixed-precision iterative refinement. A mixed-precision iterative refinement solver performs part of the solving process with high precision, and another part with lower precision to speed up the overall solution process while still providing the final result in high precision. Precision is determined by the accuracy to which values, computed during the processing operation, can be expressed in the corresponding data items. This in turn depends on the data representation, or data type, and in particular the bit-width and data format, used for data items.
The basic iterative refinement method can be expressed by the following algorithm:Ax=b
1. x0←A−1b
2. k=l
3. repeat
4. rk←b−Axk−1 
5. zk←A−1rk 
6. xk←xk−1+zk 
7. k←k+1
8. until convergence
Steps 3 to 8 represent an outer loop of the iterative process which is repeated until a convergence criterion is met. Step 5 represents an inner loop of the process. This involves solving the linear system Azk=rk in each iteration of the outer loop. A mixed-precision iterative refinement solver uses a high working precision for the outer loop and a low precision for the computationally-intensive inner loop (where the terms “high” and “low” are used here simply to distinguish different levels of precision, one being higher than the other, and do not imply any particular constraints on individual precision levels). The final result (solution vector x) is, thus, provided in high working precision. Common mixed-precision solver implementations use double-precision (64-bit) floating-point as the outer, working precision and single-precision (32-bit) floating-point as the low inner precision.
The choice of inner and outer data representations affects the performance as well as power efficiency of mixed-precision solvers in complex ways. For example, using more bits than strictly necessary per data item in the inner solver increases memory requirements and negatively affects performance of this bandwidth-bound problem. On the other hand, use of too few bits may prevent the system from converging to a final solution. The choice of data format, e.g., format type such as fixed-point or floating-point, location of the point-position, ratio of mantissa/exponent bits etc., is also important. Sub-optimal choice of data representations can thus result in poor performance in terms of power efficiency, accuracy and convergence rates, and can even cause divergence. Conventional mixed-precision iterative refinement systems use a fixed data representation that “works for most cases” for the inner solver. A typical example is single-precision float which has a high dynamic range and a reasonably good resolution for small numbers.
“AIR: Adaptive Dynamic Precision Iterative Refinement”, by J. K. Lee, http://trace.tennessee.edu/utk_graddiss/1446/, discusses a direct method for solving linear systems using a floating-point data representation. As explained on page 81 of that document, the system cancels a fixed number of most-significant mantissa bits for a residual quantity in successive iterations of the solution process, according to the predictable convergence rate of the direct solution method. This allows addition of a corresponding fixed number of least-significant mantissa bits to the residual quantity in each iteration, whereby precision steadily increases in fixed increments in successive iterations.